package com.yvon.service.demo.algorithm.offer;

/**
 * @author : Yvon
 * @since : 2022-07-19
 */
public class P11 {
    public static void main(String[] args) {
        Solution solution = new P11().new Solution();
        int[] arr = new int[]{5, 6, 1, 2, 3, 4};
        System.out.println(solution.minArray(arr));
    }


    /**
     * <img src = "https://img-blog.csdnimg.cn/82afa2e2bf4f418a931f469c673d26c1.png"/>
     * <img src = "https://img2020.cnblogs.com/blog/1213309/202104/1213309-20210411200323988-588705831.png"/>
     */
    class Solution {
        public int minArray(int[] numbers) {
            // 定义两个指针分别指向数组的左右两端
            int i = 0, j = numbers.length - 1;
            // 当i= j时挑出二分循环
            while (i < j) {
                // 取二分的中点
                int m = (i + j) >>> 1;
                if (numbers[m] > numbers[j]) {
                    // m一定在左排序数组中，即旋转点x一定在[m+1, j]闭区间内，因此执行i = m + 1;
                    i = m + 1;
                }
                if (numbers[m] < numbers[j]) {
                    // m一定在右排序数组中，即旋转点x一定在[i,m]闭区间内，因此执行j = m;
                    j = m;
                }
                if (numbers[m] == numbers[j]) {
                    // 无法判断m在那个排序数组中，既无法判断旋转点x在[i,m]还是[m+1, j]区间, 缩小范围
                    --j;
                }

            }
            return numbers[i];
        }
    }
}
